package basic.study.wantOffer.chapter3;


import java.net.Socket;

/**
 * @author Kevin
 * @date 2020/4/23 21:42
 * 二叉搜索树与双向链表
 */
public class Problem36 {

    BinaryTreeNode Convert(BinaryTreeNode root) {
        BinaryTreeNode last = null;
        last = ConvertNode(root, last);

        // last 指向双向链表的尾节点，需要返回头结点
        while (last != null && last.left != null) {
            last = last.left;
        }
        return last;
    }
    //这里不同于C++，不能在函数里修改引用对象，所以得把last节点传回来
    //返回是当前子树的尾节点
    BinaryTreeNode ConvertNode(BinaryTreeNode root, BinaryTreeNode last) {
        if (root == null) {
            return null;
        }
        BinaryTreeNode cur = root;
        //中序，先左子树
        if (root.left!=null) {
            last = ConvertNode(cur.left, last);
        }
        //尾结点与中间节点连接
        cur.left = last;
        //注意考虑空值
        if (last != null) {
            last.right = cur;
        }
        // 如果是叶子节点，那就是此为返回值
        last = cur;
        // 然后遍历右边
        if (cur.right != null) {
            last = ConvertNode(cur.right, last);
        }
        return last;
    }
    // 下次做到了，写个测试用例
    public static void main(String[] args) {

    }

    class BinaryTreeNode {
        private int data;
        private BinaryTreeNode left;
        private BinaryTreeNode right;
    }
}
